백준 2661번: 좋은 수열
성능 제약
- 메모리 제한: 128MB
- 시간 제한: 1초
문제
숫자 1, 2, 3으로만 이루어지는 수열이 있다. 임의의 길이의 인접한 두 개의 부분 수열이 동일한 것이 있으면, 그 수열을 나쁜 수열이라고 부른다.
다음은 나쁜 수열의 예이다.
- 33
- 32121323
- 123123213
다음은 좋은 수열의 예이다.
- 2
- 32
- 32123
- 1232123
길이가 N인 좋은 수열들을 N자리의 정수로 보아 그중 가장 작은 수를 나타내는 수열을 구하는 프로그램을 작성하라. 예를 들면, 1213121과 2123212는 모두 좋은 수열이지만 그 중에서 작은 수를 나타내는 수열은 1213121이다.
입력
입력은 숫자 N하나로 이루어진다. N은 1 이상 80 이하이다.
출력
첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다.
예제 입력 1
7
예제 출력 1
1213121
발단
일단 조건은, 반복적 규칙이 연속적으로 나와서는 안 된다.
12312323을 군집화하면, (123)(123)23, 1231(23)(23)이라는 2가지 경우의 수가 있다.
부분을 보자. 123123
구조(12312323의 나쁜 수열 substring, 123123)
123 / 123
Left: 123, Right: 123
("123" == "123") == true
구조(121312313의 좋은 수열 substring, 2313)
23 / 13
Left: 23, Right: 13
("23" == "13") == false
좋은 수열은 substring에서 중간을 기준으로 서로 가장 같은 길이의 서브스트링을 추출해 좌측과 우측이 동일한 l == r인 것이 존재하지 않아야 한다는 것이다.
그리고 이러한 비교는 재귀적으로 돌아갈 것이다.
123 -> 12, 23 -> (1,2), (2,3)과 같은 형태이다.
조금 더 비유적으로 설명해보자. 좋은 막대, 나쁜 막대라고 해 보자.
- 균질한 재질로 좌우 대칭으로 주조한 쇠 막대는 좋은 막대가 아니다.
- 숲에서 잘라온 울퉁불퉁한 나뭇가지는 좋은 막대이다.
전개
좋은 수열의 검증 방법을 생각해 보자. 문자열의 끝부터 최소 길이부터 비교해 보도록 하자.
나쁜 수열(12312323)
비교 길이: 1, 비교 인덱스: 6, 7
-> idx[6] == 2, idx[7] == 3
Left: 2, Right: 3
( "2" == "2" ) == false
비교 길이: 2, 비교 인덱스: idx[4] to idx[5], idx[6] to idx[7]
| index | 0 | 1 | 2 | 3 | '4' | '5' | "6" | "7" |
|---|---|---|---|---|---|---|---|---|
| value | 1 | 2 | 3 | 1 | 2 | 3 | 2 | 3 |
'Left': 23, "Right" : 23
( “23” == “23” ) == true
좋은 수열 (121312313)
길이 1, 추가 재귀 X
Left: 1 Right: 2 Left: 2 Right: 1 Left: 1 Right: 2 Left: 1 Right: 3 어떤 것도 좌우가 일치하지 않는다.
길이 2, 추가 재귀 1회
길이 2
Left: 12 Right: 13
재귀 1회차, 길이 1
Left: 3 Right: 1
Length 2
Left: 21 Right: 31
재귀 1회차, 길이 1
Left: 1 Right: 2
재귀 1회차, 길이 1
Left: 21 Right: 31
그리고 유의할 점은, 재귀 호출은 순차적으로 출력되지 않으므로 로깅으로 흐름을 따라가는 것이 제한적이다.
9
Left: 1 Right: 2
Left: 2 Right: 1
Left: 1 Right: 2
Left: 1 Right: 3
Left: 12 Right: 13
Left: 3 Right: 1
Left: 21 Right: 31
Left: 1 Right: 2
Left: 13 Right: 12
Left: 121 Right: 312
Left: 2 Right: 1
Left: 31 Right: 21
Left: 213 Right: 121
Left: 1 Right: 2
Left: 1 Right: 3
Left: 12 Right: 13
Left: 131 Right: 213
Left: 2 Right: 3
Left: 31 Right: 23
Left: 213 Right: 123
Left: 3 Right: 1
Left: 12 Right: 31
Left: 131 Right: 231
Left: 1213 Right: 1231
Left: 1 Right: 2
Left: 23 Right: 12
Left: 1 Right: 3
Left: 23 Right: 13
Left: 312 Right: 313
Left: 2131 Right: 2313
Left: 3 Right: 2
Left: 12 Right: 32
Left: 131 Right: 232
Left: 1213 Right: 1232
Left: 1 Right: 3
Left: 3 Right: 2
Left: 21 Right: 32
Left: 2 Right: 3
Left: 1 Right: 3
121312313
이와 같이 로그를 갖는다. 일부 순서가 뒤바뀌곤 한다.
발단
유의사항
for(int i = 1; i <= len / 2; i++) 지점에서 등호를 써야 적확 answer != “” (혹은!answer.equals(“”)) 에서 논리 부정을 누락하면 안 된다. 오탈자나 나기 좋은데, 만약 부등호가 아니라면 알고리즘 수행이 되기도 전의 첫번째 호출에서 아무 동작도 하지 않고 함수가 끝난다.
Java 풀이
import java.io.*;
import java.util.*;
public class Main {
static String answer = "";
static int maxCheckNumber = 3;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int len = Integer.parseInt(br.readLine());
String s = "";
createString(s, len);
bw.write(answer);
bw.flush();
}
static boolean checkValidString(String s) {
int len = s.length();
for(int i = 1; i <= len / 2; i++) {
int size = len - i * 2;
String suffix1 = s.substring(len - i, len);
String suffix2 = s.substring(len - 2 * i, len - i);
if (suffix1.equals(suffix2)) {
return false;
}
}
return true;
}
static void createString(String s, int len) {
if(!checkValidString(s)) return;
if(!answer.equals("")) return;
if(s.length() >= len) {
answer = s;
}
for(int i = 1; i <= maxCheckNumber; i++) {
createString(s+Integer.toString(i), len);
}
}
}
Java에서 등호를 이용한 스트링 비교는 권장되지 않는다. equals 등을 이용하여 비교하는 것이 보편적이다.
Javascript 풀이
function inputLength() {
let fs = require('fs')
let input = fs.readFileSync('/dev/stdin').toString().trim();
return Number(input);
}
let answer = "";
let n = 0;
let maxCheckNum = 3;
function verify(s) {
for(let i = 1; i <= s.length / 2; i++) {
let size = s.length - i * 2;
if(s.slice(size, size+i) === s.slice(size+i, size+i*2)) {
return false;
}
}
return true;
}
function goodString(s) {
if(!verify(s) || answer !== "") {
return
}
if(s.length === n) {
answer = s
return
}
for(let i = 1; i <= maxCheckNum; i++) {
goodString(s+i)
}
}
function main() {
n = inputLength()
goodString("")
console.log(answer)
}
main()
=== 비교를 통해 Type Coersion을 방지한다. 또한, slice 지점을 지정하는 것은 Go같으나 그 호출방식은 전통적인 Java, C++에 가깝다.
Python3 풀이
class problem2661:
def __init__(self):
self.answer = False
self.l = 0
def inputLength(self):
self.l = int(input())
def verify(self, s):
for i in range(1, int(len(s) / 2) + 1):
size = len(s) - i *2
if s[size: size+i] == s[size+i: size+i*2]:
return False
return True
def goodString(self, s):
if not self.verify(s) or self.answer:
return
if len(s) >= self.l:
self.answer = True
print(s)
return
for i in range(1,4):
self.goodString(s+str(i))
if self.answer:
return
def main(self):
self.inputLength()
self.goodString("")
if __name__ == "__main__":
p = problem2661()
p.main()
파이썬 풀이는 현대적이고 자연어에 가까운 언어라는 특성이 잘 반영된다. 파이썬은 초기 학습 곡선이 좋으나 후반부 학습 곡선이 대체로 확 가팔라진다. self를 이용한 클래스 구현은 직관적이고 이해하기 편하다. or, not, in-range 등의 자연어에 가까운 언어 특성은 파이썬이 이토록 빠르게 확산되는 원동력이었다. Go가 만약 이러한 키워드들을 지원했다면 파이썬의 아성을 넘볼 수 있었을까 상상해 본다.
Go 풀이
package main
import "bufio"
import "os"
import "strconv"
import "strings"
type createGoodString interface {
input()
goodString(string)
verify(string) bool
}
const MAX_CHECK_NUM = 3
type solve2661 struct {
l int //length
answer bool
iostr *bufio.ReadWriter
}
func (prob *solve2661) input() {
prob.iostr = bufio.NewReadWriter(bufio.NewReader(os.Stdin), bufio.NewWriter(os.Stdout))
var buf []byte = make([]byte, 2)
_, err := prob.iostr.Read(buf)
if err != nil {
panic(err)
}
prob.l, err = strconv.Atoi(strings.TrimRight(string(buf), "\n"))
if err != nil {
panic(err)
}
}
func (prob *solve2661) verify(s string) bool {
for i := 1; i <= len(s) / 2; i++ {
size := len(s) - i * 2;
if s[size: size+i] == s[size+i: size+i*2] {
return false
}
}
return true
}
func (prob *solve2661) goodString(s string) {
if !prob.verify(s) || prob.answer {
return
}
if len(s) >= prob.l {
prob.answer = true
prob.iostr.WriteString(s)
prob.iostr.Flush()
return
}
for i := 1; i <= MAX_CHECK_NUM; i++ {
prob.goodString(s+strconv.Itoa(i))
if prob.answer {
return
}
}
}
func main() {
p := new(solve2661)
p.input()
p.goodString("")
}
여기서는 final recursion을 bool type으로 관리했고, 인터페이스를 활용해 코드를 정리했다. C++보다도 메모리 절약적이며 성능 역시 근소한 차이인 868-872KB, 4ms의 성능을 보였다. GC가 있는 매니지드 언어에서 이 정도의 성능을 낼 수 있다는 점이 주목할 점이다. 생산성 중심의 현대 언어다운 빠르고 쉬운 슬라이싱과 단순한 문법으로 스크립트 짜듯 작성 가능하다.
CPP 풀이
#include<iostream>
#include<string>
using namespace std;
#define MAX_CHECK_NUM 3
bool check_valid(string s) {
int len = s.length();
for(int i = 1; i <= len /2 ; i++) {
int size = len - i * 2;
if(s.substr(size,i) == s.substr(size+i,i)) return false;
//len = 7
//if i == 1: len - 2 == 5 , len - 2 + 1 == 6. compare idx5 and idx6
// if i == 2: len - 4 == 3 as len 2, len - 4 + 2 == 4 as len 2. comparing idx[3-4], idx[5,6]
// .. continues
}
return true;
}
void createString(string s, string &answer, int len) {
if(!check_valid(s)) return;
if(answer.length()) return;
if(s.length() >= len) {
answer = s;
return;
}
for(int i = 1; i <= MAX_CHECK_NUM; i++) {
createString(s+to_string(i), answer, len);
if(answer.length()) return;
}
}
int main() {
string s = "", answer = "";
int len = 0;
cin >> len;
createString(s, answer, len);
cout << answer;
return 0;
}
단순하고 고전적인 풀이다. 고전 C++의 틀을 벗어나지 않았다(또한 그것이 의도이다).